package com.sort;

import java.time.temporal.ValueRange;
import java.util.Arrays;

/**
 * @author 江 岸
 * @version V1.0
 * @ClassName: SortTest
 * @description: 排序作业：插入排序，希尔排序，快速排序，归并排序，桶排序
 * @date 2021/2/2317:13
 * @since V1.0
 */
public class SortTest {
    public static void main(String[] args) {
        int[] arr = {1,6,10,7,10,4,3,16,39,9,108,900,23,4561,567};
        //insertSort(arr);
        //shellSort(arr);
        //quickSort(arr,0,arr.length-1);
        //mergeSort(arr);
        RadixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    //插入排序
    public static void insertSort(int[] arr){
        int value=0;
        int index=0;
        for (int i=1;i<arr.length;i++){
            value = arr[i];
            index = i-1;
            while (index>=0 && value<arr[index] ){
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = value;
        }
    }

    //希尔排序
    public static void shellSort(int[] arr){
        int value=0;
        int index=0;
        //先分组
        for (int n=arr.length/2;n>0;n/=2){
            //对五组分别插入排序
            for (int i=n;i<arr.length;i++){
                value = arr[i];
                index = i - n;
                while (index>=0 && value < arr[index]){
                    arr[index+n] = arr[index];
                    index = index - n;
                }
                arr[index+n] = value;
            }
        }
    }

    //快速排序
    public static void quickSort(int[] arr,int left,int right){
        int mid =  arr[(left + right)/2];
        int lIndex=left;
        int rIndex=right;
        while (lIndex<rIndex){
            while(arr[lIndex]<mid){
                lIndex++;
            }
            while(arr[rIndex]>mid){
                rIndex--;
            }
            if (lIndex>=rIndex){
                break;
            }
            int temp = arr[lIndex];
            arr[lIndex] = arr[rIndex];
            arr[rIndex] = temp;
            if (arr[lIndex] == mid){
                rIndex--;
            }
            if (arr[rIndex] == mid){
                lIndex++;
            }
        }
        if (lIndex<left) quickSort(arr,left,lIndex-1);
        if (right>rIndex) quickSort(arr,rIndex+1,right);
    }

    //归并排序
    public static void mergeSort(int[] arr){
        int[] ints = new int[arr.length];
        fen(0,arr.length-1,arr,ints);
    }
    //分
    public static void fen(int left,int right,int[] arr,int[] temp){
        if (left<right){
            int mid = (left+right)/2;
            fen(left,mid,arr,temp);
            fen(mid+1,right,arr,temp);
            merge(left,mid,right,arr,temp);
        }
    }
    //制
    public static void merge(int left,int mid,int right,int[] arr,int[] temp){
        int lo=left,ro=mid+1;
        int t = 0;
        while (lo<=mid && ro<=right){
            if (arr[lo]<arr[ro]){
                temp[t] = arr[lo];
                lo++;
            }else {
                temp[t] = arr[ro];
                ro++;
            }
            t++;
        }
        while (ro<=right){
            temp[t] = arr[ro];
            ro++;
            t++;
        }
        while (lo<=mid){
            temp[t] = arr[lo];
            lo++;
            t++;
        }
        for (int i=0;i<t;i++){
            arr[left+i] = temp[i];
        }
    }

    //基数排序
    public static void RadixSort(int[] arr){
        int[][] tong = new int[10][arr.length];
        int[] index = new int[10];
        int max = 0;
        for (int x:arr){
            max = Math.max(max,x);
        }
        max = (max+"").length();
        for (int i=0,n=1;i<max;i++,n=n*10){
            for (int j=0;j<arr.length;j++){
                int res = arr[j]/n%10;
                tong[res][index[res]++] = arr[j];
            }
            int tempIndex = 0;
            for (int k=0;k<10;k++){
                for (int x=0;x<index[k];x++){
                    arr[tempIndex++] = tong[k][x];
                }
                index[k] = 0;
            }
        }
    }
}
